import java.util.Stack;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28318
 * Date: 2025-11-11
 * Time: 15:58
 */
public class MyStackList {

    StackList head;

    public class StackList{
        int val;
        StackList next;

        public StackList(){

        }

        public StackList(int val) {
            this.val = val;
        }
    }

//    构造方法
    public MyStackList() {
        this.head = new StackList();
    }

//    入栈/压栈
    public void push(int val) {
        StackList newH = new StackList(val);
        newH.next = this.head.next;
        this.head.next = newH;
    }

//    出栈/删去栈顶节点
    public void pop() {
        if (this.head.next == null){
            return;
        }
        this.head.next = this.head.next.next;
    }

//    获取栈顶元素
    public int top() {
        return this.head.next.val;
    }

//    获取栈中最小元素
    public int getMin() {
        StackList cur = this.head.next;
        if (cur == null){
            return 0;
        }
        int min = cur.val;
        while (cur != null){
            if (min > cur.val){
                min = cur.val;
            }
            cur = cur.next;
        }
        return min;
    }

    public boolean isValid(String s) {
        Stack<Character> sta = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{'){
                sta.push(ch);
            }else {
                if (sta.empty()){
                    return false;
                }
                switch (sta.peek()){
                    case '(':
                        if (ch != ')'){
                            return false;
                        }else {
                            sta.pop();
                        }
                        break;
                    case '[':
                        if (ch != ']'){
                            return false;
                        }else {
                            sta.pop();
                        }
                        break;
                    case '{':
                        if (ch != '}'){
                            return false;
                        }else {
                            sta.pop();
                        }
                        break;
                    default:
                        break;
                }
            }
        }
        return sta.empty();
    }

    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> sta = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            sta.push(pushV[i]);
            while (!sta.empty() && j < popV.length && sta.peek() == popV[j]){
                sta.pop();
                j++;
            }
        }
        return sta.empty();
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> sta = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if (!this.isOperation(str)){
                sta.push(Integer.parseInt(str));
            }else {
                int num2 = sta.pop();
                int num1 = sta.pop();
                switch (str){
                    case "+":
                        sta.push(num1 + num2);
                        break;
                    case "-":
                        sta.push(num1 - num2);
                        break;
                    case "*":
                        sta.push(num1 * num2);
                        break;
                    case "/":
                        sta.push(num1 / num2);
                        break;
                    default:
                        break;
                }
            }
        }
        return sta.pop();
    }

    private boolean isOperation(String s){
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
            return true;
        }
        return false;
    }
}
